package com.mamingchao.basic.arraysort.shellsort;

/**
 * 升级版的 希尔排序
 * 对半切分排序，不是最快的。
 * Donald Knuth 发明的 Knuth 序列 h =1; h=3*h + 1;
 * Created by mamingchao on 2021/3/9.
 */
public class ShellSortWithKnuth {

    public static void main(String[] args) {

        int[] arr = {5,3,6,1,8,2,1,0,12,13,17,9,20,30};

        sort(arr);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }


    public static void sort(int[] arr) {
        int h = 1;
        while (h <= 1000 /3) {
            h = 3*h +1;
        }


        for (; h > 0 ; h=(h-1)/3) {
            System.out.println("h 的值为-" + h);
            for (int i = h; i < arr.length; i++) {
                for (int j = i; j > h-1; j=j-h) {
                    if (arr[j] < arr[j-h]) {
                        arr[j] = arr[j] ^ arr[j-h];
                        arr[j-h] = arr[j] ^ arr[j-h];
                        arr[j] = arr[j] ^ arr[j-h];
                    } else {
                        break;
                    }
                }
            }
        }
    }
}
